{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Points in an Archery Competition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBobPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #射箭比赛中的最大得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>Alice 先射 <code>numArrows</code> 支箭，然后 Bob 也射 <code>numArrows</code> 支箭。</li>\n",
    "\t<li>分数按下述规则计算：\n",
    "\t<ol>\n",
    "\t\t<li>箭靶有若干整数计分区域，范围从 <code>0</code> 到 <code>11</code> （含 <code>0</code> 和 <code>11</code>）。</li>\n",
    "\t\t<li>箭靶上每个区域都对应一个得分 <code>k</code>（范围是 <code>0</code> 到 <code>11</code>），Alice 和 Bob 分别在得分 <code>k</code>&nbsp;区域射中&nbsp;<code>a<sub>k</sub></code> 和 <code>b<sub>k</sub></code> 支箭。如果 <code>a<sub>k</sub> &gt;= b<sub>k</sub></code> ，那么 Alice 得 <code>k</code> 分。如果 <code>a<sub>k</sub> &lt; b<sub>k</sub></code> ，则 Bob 得 <code>k</code> 分</li>\n",
    "\t\t<li>如果 <code>a<sub>k</sub> == b<sub>k</sub> == 0</code> ，那么无人得到 <code>k</code> 分。</li>\n",
    "\t</ol>\n",
    "\t</li>\n",
    "</ol>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p>例如，Alice 和 Bob 都向计分为 <code>11</code> 的区域射 <code>2</code> 支箭，那么 Alice 得 <code>11</code> 分。如果 Alice 向计分为 <code>11</code> 的区域射 <code>0</code> 支箭，但 Bob 向同一个区域射 <code>2</code> 支箭，那么 Bob 得&nbsp;<code>11</code> 分。</p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你整数 <code>numArrows</code> 和一个长度为 <code>12</code> 的整数数组 <code>aliceArrows</code> ，该数组表示 Alice 射中&nbsp;<code>0</code> 到 <code>11</code> 每个计分区域的箭数量。现在，Bob 想要尽可能 <strong>最大化</strong> 他所能获得的总分。</p>\n",
    "\n",
    "<p>返回数组 <code>bobArrows</code><em> </em>，该数组表示 Bob 射中&nbsp;<code>0</code> 到 <code>11</code> <strong>每个</strong> 计分区域的箭数量。且 <code>bobArrows</code> 的总和应当等于 <code>numArrows</code> 。</p>\n",
    "\n",
    "<p>如果存在多种方法都可以使 Bob 获得最大总分，返回其中 <strong>任意一种</strong> 即可。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1647744752-kQKrXw-image.png\" style=\"width: 600px; height: 120px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]\n",
    "<strong>输出：</strong>[0,0,0,0,1,1,0,0,1,2,3,1]\n",
    "<strong>解释：</strong>上表显示了比赛得分情况。\n",
    "Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。\n",
    "可以证明 Bob 无法获得比 47 更高的分数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1647744785-cMHzaC-image.png\" style=\"width: 600px; height: 117px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]\n",
    "<strong>输出：</strong>[0,0,0,0,0,0,0,0,1,1,1,0]\n",
    "<strong>解释：</strong>上表显示了比赛得分情况。\n",
    "Bob 获得总分 8 + 9 + 10 = 27 。\n",
    "可以证明 Bob 无法获得比 27 更高的分数。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= numArrows &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>aliceArrows.length == bobArrows.length == 12</code></li>\n",
    "\t<li><code>0 &lt;= aliceArrows[i], bobArrows[i] &lt;= numArrows</code></li>\n",
    "\t<li><code>sum(aliceArrows[i]) == numArrows</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-points-in-an-archery-competition](https://leetcode.cn/problems/maximum-points-in-an-archery-competition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-points-in-an-archery-competition](https://leetcode.cn/problems/maximum-points-in-an-archery-competition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['9\\n[1,1,0,1,0,0,2,1,0,1,2,0]', '3\\n[0,0,1,0,0,0,0,0,0,0,0,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "        maxscore = -1\n",
    "        for i in range(1 << 12):\n",
    "            \n",
    "            score, arrow, bobArrows = 0, 0, [0] * 12\n",
    "\n",
    "            for j, arr in enumerate(aliceArrows):\n",
    "\n",
    "                if i >> j & 1 == 1:\n",
    "                    score += j\n",
    "                    arrow += arr + 1\n",
    "                    bobArrows[j] = arr + 1\n",
    "            \n",
    "            if arrow > numArrows:\n",
    "                continue\n",
    "\n",
    "            if score > maxscore:\n",
    "\n",
    "                maxscore = score\n",
    "                bobArrows[0] += numArrows - arrow\n",
    "                res = bobArrows[:]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "        maxscore = -1\n",
    "        for i in range(1 << 12):\n",
    "            \n",
    "            score, arrow, bobArrows = 0, 0, [0] * 12\n",
    "\n",
    "            for j, arr in enumerate(aliceArrows):\n",
    "\n",
    "                if i >> j & 1 == 1:\n",
    "                    score += j\n",
    "                    arrow += arr + 1\n",
    "                    bobArrows[j] = arr + 1\n",
    "            \n",
    "            if arrow > numArrows:\n",
    "                continue\n",
    "\n",
    "            if score > maxscore:\n",
    "\n",
    "                maxscore = score\n",
    "                bobArrows[0] += numArrows - arrow\n",
    "                res = bobArrows[:]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        n = len(aliceArrows)\n",
    "        state = 0\n",
    "        maxscore = 0\n",
    "\n",
    "        # 枚举的在每个区域的胜负状态\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = 0\n",
    "            score = 0\n",
    "            # 对每个区域进行计数\n",
    "            for i in range(12):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += aliceArrows[i] + 1\n",
    "                    score += i\n",
    "            # 更新状态\n",
    "            if cnt <= numArrows and score > maxscore:\n",
    "                maxscore = score\n",
    "                state = mask\n",
    "        \n",
    "        ans = [0] * n\n",
    "        cnt = numArrows\n",
    "        for i in range(n):\n",
    "            if state >> i & 1:\n",
    "                ans[i] = aliceArrows[i] + 1\n",
    "                cnt -= ans[i]\n",
    "        if cnt > 0:\n",
    "            ans[0] += cnt\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        res = [0] * 12\n",
    "        max_score = 0\n",
    "\n",
    "        for state in range(4096):\n",
    "            score = 0\n",
    "            cnt = 0\n",
    "            now = [0] * 12\n",
    "            for index in range(12):\n",
    "                if state & (1 << index):\n",
    "                    now[index] = aliceArrows[index] + 1\n",
    "                    cnt += now[index]\n",
    "                    score += index\n",
    "            \n",
    "            if cnt <= numArrows and score > max_score:\n",
    "                max_score = score\n",
    "                res = now[:]\n",
    "                res[0] += numArrows - cnt\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        ans=0\n",
    "        maxscore=-1\n",
    "        nm=len(aliceArrows)\n",
    "        \n",
    "        dp=[0 for i in range(nm)]\n",
    "        for state in range(1<<nm):\n",
    "            score=0\n",
    "            needarr=0\n",
    "            for p in range(nm):\n",
    "                if state&(1<<p): \n",
    "                    tmp=aliceArrows[p]+1\n",
    "                    score+=p\n",
    "                else: \n",
    "                    tmp=0\n",
    "                dp[p]=tmp\n",
    "                needarr+=tmp\n",
    "                if needarr>numArrows: break\n",
    "            \n",
    "            if needarr<=numArrows:\n",
    "                maxscore=max(maxscore,score)\n",
    "                if maxscore==score:\n",
    "                    res=dp[:]\n",
    "                    for k in range(nm):\n",
    "                        if state&(1<<k):\n",
    "                            res[k]+=numArrows-needarr\n",
    "                            break\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "        def f(i, left):\n",
    "            if i == 0:\n",
    "                if left > aliceArrows[i]:\n",
    "                    return i, [left]\n",
    "                else:\n",
    "                    return 0, [left]\n",
    "            if left > aliceArrows[i]:\n",
    "                x1, y1 = f(i - 1, left - aliceArrows[i] - 1)\n",
    "                x1 += i \n",
    "                x2, y2 = f(i - 1, left)\n",
    "                if x1 > x2:\n",
    "                    return x1, y1 + [aliceArrows[i] + 1]\n",
    "                else:\n",
    "                    return x2, y2 + [0]\n",
    "            else:\n",
    "                x, y = f(i - 1, left)\n",
    "                return x, y + [0]\n",
    "        \n",
    "        return f(len(aliceArrows) - 1, numArrows)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        ans=0\n",
    "        ansl=[0]*12\n",
    "        def dfs(pos,l,score):\n",
    "            nonlocal ans\n",
    "            nonlocal ansl\n",
    "            if pos==12:\n",
    "                if sum(l)<=numArrows and score>ans:\n",
    "                    ans=max(ans,score)\n",
    "                    ansl=l.copy()\n",
    "\n",
    "                return\n",
    "\n",
    "            dfs(pos+1,l,score)\n",
    "            l[pos]=aliceArrows[pos]+1\n",
    "            dfs(pos+1,l,score+pos)\n",
    "            l[pos]=0\n",
    "        dfs(0,[0]*12,0)\n",
    "\n",
    "\n",
    "\n",
    "        if sum(ansl)<numArrows:\n",
    "            ansl[-1]+=numArrows-sum(ansl)\n",
    "        return ansl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        n = len(aliceArrows)\n",
    "        maxscore = 0   # 可行的最大得分\n",
    "        state = 0   # 对应状态\n",
    "        # 枚举所有输赢状态\n",
    "        for mask in range(1 << n):\n",
    "            cnt = 0\n",
    "            score = 0\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    cnt += aliceArrows[i] + 1\n",
    "                    score += i\n",
    "            if cnt <= numArrows and score > maxscore:\n",
    "                # 可行，且更新了当前最大得分\n",
    "                maxscore = score\n",
    "                state = mask\n",
    "        # 通过状态构造一种可行方法\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            if (state >> i) & 1:\n",
    "                res[i] = aliceArrows[i] + 1\n",
    "                numArrows -= res[i]\n",
    "        res[0] += numArrows\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        n = len(aliceArrows)\n",
    "        maxscore = 0   # 可行的最大得分\n",
    "        state = 0   # 对应状态\n",
    "        # 枚举所有输赢状态\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = 0\n",
    "            score = 0\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    cnt += aliceArrows[i] + 1\n",
    "                    score += i\n",
    "            if cnt <= numArrows and score > maxscore:\n",
    "                # 可行，且更新了当前最大得分\n",
    "                maxscore = score\n",
    "                state = mask\n",
    "        # 通过状态构造一种可行方法\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            if (state >> i) & 1:\n",
    "                res[i] = aliceArrows[i] + 1\n",
    "                numArrows -= res[i]\n",
    "        res[0] += numArrows\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        maxScore = -1\n",
    "        ans = [0] * 12  # Initialize bobArrows with 0 arrows for each position\n",
    "\n",
    "        for i in range(1 << len(aliceArrows)):  # Binary enumeration\n",
    "            score = 0\n",
    "            arrow = 0\n",
    "            bobArrows = [0] * 12\n",
    "\n",
    "            for j, v in enumerate(aliceArrows):\n",
    "                if (i >> j) & 1 == 1:  # Check if Alice used the arrow\n",
    "                    score += j\n",
    "                    arrow += v + 1\n",
    "                    bobArrows[j] = v + 1  # Bob takes one extra arrow\n",
    "\n",
    "            if arrow > numArrows:\n",
    "                continue\n",
    "\n",
    "            if score > maxScore:\n",
    "                maxScore = score\n",
    "                bobArrows[0] += numArrows - arrow  # Fill the first position to reach numArrows\n",
    "                ans = bobArrows[:]\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        n = len(aliceArrows)\n",
    "        maxscore = 0   # 可行的最大得分\n",
    "        state = 0   # 对应状态\n",
    "        # 枚举所有输赢状态\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = 0\n",
    "            score = 0\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    cnt += aliceArrows[i] + 1\n",
    "                    score += i\n",
    "            if cnt <= numArrows and score > maxscore:\n",
    "                # 可行，且更新了当前最大得分\n",
    "                maxscore = score\n",
    "                state = mask\n",
    "        # 通过状态构造一种可行方法\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            if (state >> i) & 1:\n",
    "                res[i] = aliceArrows[i] + 1\n",
    "                numArrows -= res[i]\n",
    "        res[0] += numArrows\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        BobArrows = [i + 1 for i in aliceArrows]\n",
    "        total = 0\n",
    "        res = 0\n",
    "        for i in range(1, 2 ** 12):\n",
    "            temp = i\n",
    "            count = 0\n",
    "            j = 1\n",
    "            ans = 0\n",
    "            while temp > 0:\n",
    "                if temp % 2:\n",
    "                    count += BobArrows[j - 1]\n",
    "                    ans += j - 1\n",
    "                temp >>= 1\n",
    "                j += 1\n",
    "            if count <= numArrows and total < ans:\n",
    "                total = ans\n",
    "                res = i\n",
    "        nums = [0] * 12\n",
    "        while res > 0:\n",
    "            per = 1\n",
    "            while res > 0:\n",
    "                if res % 2:\n",
    "                    nums[per -1] = BobArrows[per - 1]\n",
    "                per += 1\n",
    "                res >>= 1\n",
    "        nums[0] += numArrows - sum(nums)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, n: int, a: List[int]) -> List[int]:\n",
    "        l = len(a)\n",
    "        def dfs(i, c):\n",
    "            if i == l - 1:#如果只剩最后一个区域了,那么把所有箭都射出去\n",
    "                if c > a[i]:#得分\n",
    "                    return i, [c]\n",
    "                else:#不得分\n",
    "                    return 0, [c]\n",
    "            if c > a[i]:#如果可以得分\n",
    "                x1, y1 = dfs(i + 1, c - a[i] - 1)#拿分的选择\n",
    "                x1 += i\n",
    "                x2, y2 = dfs(i + 1, c)#不拿分的选择\n",
    "                if x1 > x2:#选择得分和不得分的最优解\n",
    "                    return x1, [a[i] + 1] + y1\n",
    "                else:\n",
    "                    return x2, [0] + y2\n",
    "            else:#剩余箭的数量已经不能得分,直接去下一个区域\n",
    "                x, y = dfs(i + 1, c)\n",
    "                return x, [0] + y\n",
    "        return dfs(0, n)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        maxscore = 0\n",
    "        maxmask = 0\n",
    "        n = len(aliceArrows)\n",
    "\n",
    "\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = 0\n",
    "            score = 0\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    cnt += aliceArrows[i] + 1\n",
    "                    score += i\n",
    "            if cnt <= numArrows and score > maxscore:\n",
    "                maskmask = mask\n",
    "                maxscore = score\n",
    "        \n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            if maskmask >> i & 1:\n",
    "                ans[i] = aliceArrows[i] + 1\n",
    "        ans[0] = numArrows - sum(ans)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, n: int, a: List[int]) -> List[int]:\n",
    "        l = len(a)\n",
    "        def dfs(i, c):\n",
    "            if i == l - 1:#如果只剩最后一个区域了,那么把所有箭都射出去\n",
    "                if c > a[i]:#得分\n",
    "                    return i, [c]\n",
    "                else:#不得分\n",
    "                    return 0, [c]\n",
    "            if c > a[i]:#如果可以得分\n",
    "                x1, y1 = dfs(i + 1, c - a[i] - 1)#拿分的选择\n",
    "                x1 += i\n",
    "                x2, y2 = dfs(i + 1, c)#不拿分的选择\n",
    "                if x1 > x2:#选择得分和不得分的最优解\n",
    "                    return x1, [a[i] + 1] + y1\n",
    "                else:\n",
    "                    return x2, [0] + y2\n",
    "            else:#剩余箭的数量已经不能得分,直接去下一个区域\n",
    "                x, y = dfs(i + 1, c)\n",
    "                return x, [0] + y\n",
    "        return dfs(0, n)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        n = len(aliceArrows)\n",
    "        maxscore = 0   # 可行的最大得分\n",
    "        state = 0   # 对应状态\n",
    "        # 枚举所有输赢状态\n",
    "        for mask in range(2 ** n):\n",
    "            cnt = 0\n",
    "            score = 0\n",
    "            for i in range(n):\n",
    "                if (mask >> i) & 1:\n",
    "                    cnt += aliceArrows[i] + 1\n",
    "                    score += i\n",
    "            if cnt <= numArrows and score > maxscore:\n",
    "                # 可行，且更新了当前最大得分\n",
    "                maxscore = score\n",
    "                state = mask\n",
    "        # 通过状态构造一种可行方法\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            if (state >> i) & 1:\n",
    "                res[i] = aliceArrows[i] + 1\n",
    "                numArrows -= res[i]\n",
    "        res[0] += numArrows\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        max_score = 0\n",
    "        cost = [i + 1 for i in aliceArrows]\n",
    "        for x in range(1, 2**12):\n",
    "            tmp = [0] * 12\n",
    "            score = 0\n",
    "            for i in range(12):\n",
    "                if x & (1 << i):\n",
    "                    tmp[i] = cost[i]\n",
    "                    score += i\n",
    "            if sum(tmp) <= numArrows and score > max_score:\n",
    "                res = tmp\n",
    "                res[0] += (numArrows - sum(tmp))\n",
    "                max_score = score\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        # 核心思想：二进制枚举\n",
    "        # 枚举bob赢的情况\n",
    "        n = len(aliceArrows)\n",
    "        max_v = 0\n",
    "        active = 0\n",
    "        for i in range(1<<n):\n",
    "            cnt = 0\n",
    "            s = 0\n",
    "            for j in range(n):\n",
    "                if i&(1 << j):\n",
    "                    cnt += aliceArrows[j]+1\n",
    "                    s += j\n",
    "            if cnt <= numArrows and s > max_v:\n",
    "                max_v = s\n",
    "                active = i\n",
    "        # 知道状态了，只需要统计结果\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            if active&(1 << i):\n",
    "                ans[i] = aliceArrows[i]+1\n",
    "                numArrows -= aliceArrows[i]+1\n",
    "        ans[0] += numArrows\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        target = [0] * 12\n",
    "        ret = 0\n",
    "        rets = \"000000000000\"\n",
    "        retmp = 0\n",
    "        for i in range(12):\n",
    "            target[i] = aliceArrows[i] + 1\n",
    "        for score in range(2**12-1,-1,-1):\n",
    "            s = bin(score)[2:][::-1]\n",
    "            s += \"0\" * (12 - len(s))\n",
    "            \n",
    "            tmp = 0\n",
    "            cnt = 0\n",
    "            for i in range(12):\n",
    "                if s[i] == \"1\":\n",
    "                    tmp += target[i]\n",
    "                    cnt += i\n",
    "            if tmp <= numArrows and cnt > ret:\n",
    "                ret = cnt\n",
    "                rets = s\n",
    "                retmp = tmp\n",
    "\n",
    "        #print(ret,rets,retmp)\n",
    "        ans = []\n",
    "        for i in range(12):\n",
    "            if rets[i] == \"1\":\n",
    "                ans.append(target[i])\n",
    "            else:\n",
    "                ans.append(0)\n",
    "        ans[0] += numArrows - retmp\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        # 网友的写法\n",
    "        def dfs(remainingArrows,pos,finalScores):\n",
    "            nonlocal maxScore,ans\n",
    "            if pos > 11:\n",
    "                if remainingArrows >= 0 and finalScores > maxScore:\n",
    "                    maxScore = finalScores\n",
    "                    ans = tmp[:]\n",
    "                    ans[0] = remainingArrows\n",
    "                return\n",
    "            tmp[pos] = aliceArrows[pos] + 1\n",
    "            dfs(remainingArrows - aliceArrows[pos] - 1,pos + 1,finalScores + pos)\n",
    "            tmp[pos] = 0\n",
    "            dfs(remainingArrows,pos + 1,finalScores)\n",
    "\n",
    "        tmp = [0 for _ in range(12)]\n",
    "        maxScore = 0\n",
    "        ans = tmp\n",
    "        dfs(numArrows,1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        max_score = 0\n",
    "        ans = []\n",
    "\n",
    "        def dfs(i, score, num, f):\n",
    "            if i == 12:\n",
    "                nonlocal max_score\n",
    "                if score > max_score:\n",
    "                    nonlocal ans\n",
    "                    ans = [num] + f[1:]\n",
    "                    max_score = score\n",
    "                return\n",
    "\n",
    "            f.append(0)\n",
    "            dfs(i+1, score, num, f)\n",
    "            f.pop()\n",
    "\n",
    "            if num > aliceArrows[i]:\n",
    "                f.append(aliceArrows[i]+1)\n",
    "                dfs(i+1, score+i, num - aliceArrows[i] - 1, f)\n",
    "                f.pop()\n",
    "            \n",
    "        dfs(0, 0, numArrows, [])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(aliceArrows)\n",
    "\n",
    "\n",
    "        def backtrack(idx, cnt):\n",
    "\n",
    "            if idx == n - 1:\n",
    "                if cnt > aliceArrows[idx]:\n",
    "                    return idx, [cnt]\n",
    "                else:\n",
    "                    return 0, [cnt]\n",
    "\n",
    "            if cnt > aliceArrows[idx]: # 可以得分\n",
    "                x1, y1 = backtrack(idx + 1, cnt - aliceArrows[idx] - 1)\n",
    "                x1 += idx\n",
    "                x2, y2 = backtrack(idx + 1, cnt)\n",
    "\n",
    "                if x1 > x2:\n",
    "                    return x1, [aliceArrows[idx] + 1] + y1\n",
    "                else:\n",
    "\n",
    "                    return x2, [0] + y2\n",
    "\n",
    "            else:\n",
    "\n",
    "                x, y = backtrack(idx + 1, cnt)\n",
    "                return x, [0] + y\n",
    "\n",
    "        return backtrack(0, numArrows)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(aliceArrows)\n",
    "\n",
    "\n",
    "        def backtrack(idx, cnt):\n",
    "\n",
    "            if idx == n - 1:\n",
    "                if cnt > aliceArrows[idx]:\n",
    "                    return idx, [cnt]\n",
    "                else:\n",
    "                    return 0, [cnt]\n",
    "\n",
    "            if cnt > aliceArrows[idx]: # 可以得分\n",
    "                x1, y1 = backtrack(idx + 1, cnt - aliceArrows[idx] - 1)\n",
    "                x1 += idx\n",
    "                x2, y2 = backtrack(idx + 1, cnt)\n",
    "\n",
    "                if x1 > x2:\n",
    "                    return x1, [aliceArrows[idx] + 1] + y1\n",
    "                else:\n",
    "\n",
    "                    return x2, [0] + y2\n",
    "\n",
    "            else:\n",
    "\n",
    "                x, y = backtrack(idx + 1, cnt)\n",
    "                return x, [0] + y\n",
    "\n",
    "        return backtrack(0, numArrows)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        \n",
    "        res = []\n",
    "        points = 0\n",
    "\n",
    "        def bt(n_arrow, index, value, result):\n",
    "            nonlocal points\n",
    "            nonlocal res\n",
    "            if index == 12:\n",
    "                if value > points:\n",
    "                    points = value\n",
    "                    res = result\n",
    "                    res[11] += n_arrow\n",
    "                return\n",
    "            \n",
    "            # take\n",
    "            if n_arrow - aliceArrows[index] - 1 >=0 :\n",
    "                bt(n_arrow - aliceArrows[index] - 1, index+1, value+index, result+[aliceArrows[index]+1])\n",
    "            # not take\n",
    "            bt(n_arrow, index+1, value, result+[0])\n",
    "        bt(numArrows,0,0,[])\n",
    "        print(points)\n",
    "        return res           \n",
    "                 \n",
    "    \n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        tot = numArrows\n",
    "        a = aliceArrows\n",
    "        n = len(a)\n",
    "        mx, ans = 0, []\n",
    "        for i in range(1, 1 << n):\n",
    "            s, t = tot, [0] * n\n",
    "            sc = 0\n",
    "            ok = True\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    sc += j\n",
    "                    if s > a[j]:\n",
    "                        s -= a[j] + 1\n",
    "                        t[j] = a[j] + 1\n",
    "                    else:\n",
    "                        ok = False\n",
    "                        break\n",
    "            if s > 0:\n",
    "                t[0] += s\n",
    "            if ok and sc > mx:\n",
    "                mx, ans = sc, t\n",
    "        return ans \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "#         @cache\n",
    "#         def dfs(i, left):\n",
    "#             if i == n or left == 0:\n",
    "#                 nonlocal ans, mx\n",
    "#                 s = sum(i for i, _ in tmp)\n",
    "#                 if s > mx:\n",
    "#                     mx = s\n",
    "#                     ans = tmp[::]\n",
    "#                     print(f'{tmp}')\n",
    "#                 return\n",
    "#             dfs(i + 1, left)\n",
    "#             x = aliceArrows[i]\n",
    "#             if left > x:\n",
    "#                 tmp.append((i, x + 1))\n",
    "#                 dfs(i + 1, left - x - 1)\n",
    "#                 tmp.pop()\n",
    "                \n",
    "#         tmp = []\n",
    "#         ans, mx = [], 0\n",
    "#         n = len(aliceArrows)\n",
    "#         dfs(1, numArrows)\n",
    "#         return mx\n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        n = len(aliceArrows)\n",
    "        ans = [0]*n\n",
    "        ans[0] = numArrows\n",
    "        res = 0\n",
    "        for i in range(1<<n):\n",
    "            lst = [0]*n\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                if i & (1<<j):\n",
    "                    lst[j] = aliceArrows[j] + 1\n",
    "                    cur += j\n",
    "            s = sum(lst)\n",
    "            if s <= numArrows:\n",
    "                lst[0] += numArrows - s\n",
    "                if cur > res:\n",
    "                    res = cur\n",
    "                    ans = lst[:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(aliceArrows)\n",
    "        def backtrack(idx, cnt):\n",
    "            if idx == n - 1:\n",
    "                if cnt > aliceArrows[idx]:\n",
    "                    return idx, [cnt]\n",
    "                else:\n",
    "                    return 0, [cnt]\n",
    "            if cnt > aliceArrows[idx]: # 可以得分\n",
    "                x1, y1 = backtrack(idx + 1, cnt - aliceArrows[idx] - 1)\n",
    "                x1 += idx\n",
    "                x2, y2 = backtrack(idx + 1, cnt)\n",
    "\n",
    "                if x1 > x2:\n",
    "                    return x1, [aliceArrows[idx] + 1] + y1\n",
    "                else:\n",
    "\n",
    "                    return x2, [0] + y2\n",
    "            else:\n",
    "\n",
    "                x, y = backtrack(idx + 1, cnt)\n",
    "                return x, [0] + y\n",
    "\n",
    "        return backtrack(0, numArrows)[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        def f(n, i):\n",
    "            if i == 0:\n",
    "                return 0, [n,]\n",
    "            ans, nums = f(n, i-1)\n",
    "            if n > aliceArrows[i]:\n",
    "                a,b = f(n-aliceArrows[i]-1, i-1)\n",
    "                if i+a > ans:\n",
    "                    return i+a, b+[aliceArrows[i]+1,]\n",
    "            return ans, nums+[0,]\n",
    "\n",
    "        a,b=f(numArrows, len(aliceArrows)-1)\n",
    "        return b\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        b = [0] * 12\n",
    "        ans = []\n",
    "        mx = 0\n",
    "        def dfs(i, r, s):\n",
    "            nonlocal mx, ans\n",
    "            if i == 12:\n",
    "                if s > mx:\n",
    "                    mx = s\n",
    "                    ans = b[:]\n",
    "                return\n",
    "            if i == 11:\n",
    "                b[i] = r\n",
    "                if r > aliceArrows[i]:\n",
    "                    dfs(i + 1, 0, s + i)\n",
    "                else:\n",
    "                    dfs(i + 1, 0, s)\n",
    "            if r > aliceArrows[i]:\n",
    "                b[i] = aliceArrows[i] + 1\n",
    "                dfs(i + 1, r - aliceArrows[i] - 1, s + i)\n",
    "                b[i] = 0\n",
    "                dfs(i + 1, r, s)\n",
    "            else:\n",
    "                b[i] = 0\n",
    "                dfs(i + 1, r, s)\n",
    "        \n",
    "        dfs(0, numArrows, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        # 我这个思路没有问题，但是求解的目标错了！\n",
    "        def dfs(pos,curScore,remainingArrows):\n",
    "            nonlocal maxScore,ans\n",
    "            if pos == 12:\n",
    "                if curScore > maxScore:\n",
    "                    maxScore = curScore\n",
    "                    bobArrows[0] += remainingArrows\n",
    "                    ans = bobArrows[:]\n",
    "                    bobArrows[0] -= remainingArrows\n",
    "                return\n",
    "            # 选\n",
    "            if remainingArrows >= aliceArrows[pos] + 1:\n",
    "                remainingArrows -= aliceArrows[pos] + 1\n",
    "                curScore += pos\n",
    "                bobArrows[pos] = aliceArrows[pos] + 1\n",
    "                dfs(pos + 1,curScore,remainingArrows)\n",
    "                bobArrows[pos] = 0\n",
    "                curScore -= pos\n",
    "                remainingArrows += aliceArrows[pos] + 1\n",
    "                dfs(pos + 1,curScore,remainingArrows)\n",
    "            # 不选\n",
    "            else:\n",
    "                dfs(pos + 1,curScore,remainingArrows)\n",
    "\n",
    "        bobArrows = [0] * 12\n",
    "        maxScore = 0\n",
    "        ans = bobArrows\n",
    "        dfs(0,0,numArrows)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBobPoints(self, numArrows: int, aliceArrows: List[int]) -> List[int]:\n",
    "        D = [0] * 12\n",
    "        for i in range(1,12):\n",
    "            D[i] = aliceArrows[i]+1\n",
    "            \n",
    "        MN = [0] * 12\n",
    "        for i in range(1,12):\n",
    "            MN[i] = min(MN[i-1],D[i])\n",
    "        mx = 0  \n",
    "        \n",
    "        \n",
    "        def f(L):\n",
    "            res = 0\n",
    "            for idx,i in enumerate(L):\n",
    "                if i:res += idx\n",
    "            return res\n",
    "        \n",
    "        temp = [0] * 12\n",
    "        Res = [0] * 12\n",
    "        def dfs(k,pos):\n",
    "            nonlocal mx,Res\n",
    "            if k < 0:return\n",
    "            if pos == 0 or k < MN[pos]:\n",
    "                temp[0] = k\n",
    "                v = f(temp)\n",
    "                if mx < v:\n",
    "                    Res = temp.copy()\n",
    "                    mx = v\n",
    "                temp[0] = 0\n",
    "                return \n",
    "            dfs(k,pos-1)\n",
    "            temp[pos] = D[pos]\n",
    "            dfs(k-D[pos],pos-1)\n",
    "            temp[pos] = 0\n",
    "            return \n",
    "        dfs(numArrows,11)\n",
    "        return Res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
